package algorithmExample.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author: zhangrongqing
 * @Date: 2019/11/28 10:02
 */
//题目：https://leetcode-cn.com/problems/recover-binary-search-tree/
public class RecoverBinarySearchTree {
    public void recoverTree(TreeNode root) {
        List<TreeNode> list = sortByBefore(root);
        Integer start = 0, end = 0;
        List<Integer> tmpPos = hasWrongPos(list);
        if (tmpPos.size() != 0) {
            TreeNode leftNode = list.get(tmpPos.get(0));
            TreeNode rightNode = list.get(tmpPos.get(1));
            Integer tmp = leftNode.val;
            leftNode.val = rightNode.val;
            rightNode.val = tmp;
        }
        System.out.println(root);
    }

    private List<Integer> hasWrongPos(List<TreeNode> list) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i).val > list.get(i + 1).val) {
                if (result.size() == 0) {
                    result.add(i);
                } else {
                    result.add(i + 1);
                }
            }
        }
        return result;
    }

    private List<TreeNode> sortByBefore(TreeNode root) {
        List result = new ArrayList();
        Stack<TreeNode> stack = new Stack<>();
        while (true) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode currentNode = stack.pop();
            result.add(currentNode);
            if (currentNode.right != null) {
                root = currentNode.right;
            }
            if (stack.size() == 0) {
                break;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Integer[] input = new Integer[]{1, 3, null, null, 2};
        TreeNode treeNode = TreeUtil.toTree(input);
        List<TreeNode> result = new RecoverBinarySearchTree().sortByBefore(treeNode);
        result.stream().forEach(content -> System.out.println(content));

        new RecoverBinarySearchTree().recoverTree(treeNode);
    }
}
